Search Results

Documents authored by Cachin, Christian

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.12
Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks

Authors: Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead.
Cite as

Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo. Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.OPODIS.2023.12,
  author =	{Alpos, Orestis and Amores-Sesar, Ignacio and Cachin, Christian and Yeo, Michelle},
  title =	{{Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.12},
  URN =		{urn:nbn:de:0030-drops-195029},
  doi =		{10.4230/LIPIcs.OPODIS.2023.12},
  annote =	{Keywords: Consensus, MEV, Byzantine behavior, Rational behavior}
}
Document
DOI: 10.4230/LIPIcs.AFT.2023.16
Pay Less for Your Privacy: Towards Cost-Effective On-Chain Mixers

Authors: Zhipeng Wang, Marko Cirkovic, Duc V. Le, William Knottenbelt, and Christian Cachin

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
On-chain mixers, such as Tornado Cash (TC), have become a popular privacy solution for many non-privacy-preserving blockchain users. These mixers enable users to deposit a fixed amount of coins and withdraw them to another address, while effectively reducing the linkability between these addresses and securely obscuring their transaction history. However, the high cost of interacting with existing on-chain mixer smart contracts prohibits standard users from using the mixer, mainly due to the use of computationally expensive cryptographic primitives. For instance, the deposit cost of TC on Ethereum is approximately 1.1M gas (i.e., 66 USD in June 2023), which is 53× higher than issuing a base transfer transaction. In this work, we introduce the Merkle Pyramid Builder approach, to incrementally build the Merkle tree in an on-chain mixer and update the tree per batch of deposits, which can therefore decrease the overall cost of using the mixer. Our evaluation results highlight the effectiveness of this approach, showcasing a significant reduction of up to 7× in the amortized cost of depositing compared to state-of-the-art on-chain mixers. Importantly, these improvements are achieved without compromising users' privacy. Furthermore, we propose the utilization of verifiable computations to shift the responsibility of Merkle tree updates from on-chain smart contracts to off-chain clients, which can further reduce deposit costs. Additionally, our analysis demonstrates that our designs ensure fairness by distributing Merkle tree update costs among clients over time.
Cite as

Zhipeng Wang, Marko Cirkovic, Duc V. Le, William Knottenbelt, and Christian Cachin. Pay Less for Your Privacy: Towards Cost-Effective On-Chain Mixers. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 16:1-16:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.AFT.2023.16,
  author =	{Wang, Zhipeng and Cirkovic, Marko and Le, Duc V. and Knottenbelt, William and Cachin, Christian},
  title =	{{Pay Less for Your Privacy: Towards Cost-Effective On-Chain Mixers}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{16:1--16:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.16},
  URN =		{urn:nbn:de:0030-drops-192050},
  doi =		{10.4230/LIPIcs.AFT.2023.16},
  annote =	{Keywords: Privacy, Blockchain, Mixers, Merkle Tree}
}
Document
DOI: 10.4230/LIPIcs.AFT.2023.31
Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast

Authors: Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, and Jesper Buus Nielsen

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
We present simple and practical protocols for generating randomness as used by asynchronous total-order broadcast. The protocols are secure in a proof-of-stake setting with dynamically changing stake. They can be plugged into existing protocols for asynchronous total-order broadcast and will turn these into asynchronous total-order broadcast with dynamic stake. Our contribution relies on two important techniques. The paper "Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography" [Cachin, Kursawe, and Shoup, PODC 2000] has influenced the design of practical total-order broadcast through its use of threshold cryptography. However, it needs a setup protocol to be efficient. In a proof-of-stake setting with dynamic stake this setup would have to be continually recomputed, making the protocol impractical. The work "Asynchronous Byzantine Agreement with Subquadratic Communication" [Blum, Katz, Liu-Zhang, and Loss, TCC 2020] showed how to use an initial setup for broadcast to asymptotically efficiently generate sub-sequent setups. The protocol, however, resorted to fully homomorphic encryption and was therefore not practically efficient. We adopt their approach to the proof-of-stake setting with dynamic stake, apply it to the Constantinople paper, and remove the need for fully homomorphic encryption. This results in simple and practical proof-of-stake protocols.
Cite as

Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, and Jesper Buus Nielsen. Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.AFT.2023.31,
  author =	{Alpos, Orestis and Cachin, Christian and Kamp, Simon Holmgaard and Nielsen, Jesper Buus},
  title =	{{Practical Large-Scale Proof-Of-Stake Asynchronous Total-Order Broadcast}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.31},
  URN =		{urn:nbn:de:0030-drops-192203},
  doi =		{10.4230/LIPIcs.AFT.2023.31},
  annote =	{Keywords: Total-Order Broadcast, Atomic Broadcast, Proof of Stake, Random Beacon}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.10
When Is Spring Coming? A Security Analysis of Avalanche Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Avalanche is a blockchain consensus protocol with exceptionally low latency and high throughput. This has swiftly established the corresponding token as a top-tier cryptocurrency. Avalanche achieves such remarkable metrics by substituting proof of work with a random sampling mechanism. The protocol also differs from Bitcoin, Ethereum, and many others by forming a directed acyclic graph (DAG) instead of a chain. It does not totally order all transactions, establishes a partial order among them, and accepts transactions in the DAG that satisfy specific properties. Such parallelism is widely regarded as a technique that increases the efficiency of consensus. Despite its success, Avalanche consensus lacks a complete abstract specification and a matching formal analysis. To address this drawback, this work provides first a detailed formulation of Avalanche through pseudocode. This includes features that are omitted from the original whitepaper or are only vaguely explained in the documentation. Second, the paper gives an analysis of the formal properties fulfilled by Avalanche in the sense of a generic broadcast protocol that only orders related transactions. Last but not least, the analysis reveals a vulnerability that affects the liveness of the protocol. A possible solution that addresses the problem is also proposed.
Cite as

Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi. When Is Spring Coming? A Security Analysis of Avalanche Consensus. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2022.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Tedeschi, Enrico},
  title =	{{When Is Spring Coming? A Security Analysis of Avalanche Consensus}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.10},
  URN =		{urn:nbn:de:0030-drops-176307},
  doi =		{10.4230/LIPIcs.OPODIS.2022.10},
  annote =	{Keywords: Avalanche, security analysis, generic broadcast}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.17
Quorum Systems in Permissionless Networks

Authors: Christian Cachin, Giuliano Losa, and Luca Zanolini

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Fail-prone systems, and their quorum systems, are useful tools for the design of distributed algorithms. However, fail-prone systems as studied so far require every process to know the full system membership in order to guarantee safety through globally intersecting quorums. Thus, they are of little help in an open, permissionless setting, where such knowledge may not be available. We propose to generalize the theory of fail-prone systems to make it applicable to permissionless systems. We do so by enabling processes not only to make assumptions about failures, but also to make assumptions about the assumptions of other processes. Thus, by transitivity, processes that do not even know of any common process may nevertheless have intersecting quorums and solve, for example, reliable broadcast. Our model generalizes existing models such as the classic fail-prone system model [Malkhi and Reiter, 1998] and the asymmetric fail-prone system model [Cachin and Tackmann, OPODIS 2019]. Moreover, it gives a characterization with standard formalism of the model used by the Stellar blockchain.
Cite as

Christian Cachin, Giuliano Losa, and Luca Zanolini. Quorum Systems in Permissionless Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.OPODIS.2022.17,
  author =	{Cachin, Christian and Losa, Giuliano and Zanolini, Luca},
  title =	{{Quorum Systems in Permissionless Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{17:1--17:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.17},
  URN =		{urn:nbn:de:0030-drops-176379},
  doi =		{10.4230/LIPIcs.OPODIS.2022.17},
  annote =	{Keywords: Permissionless systems, fail-prone system, quorum system}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.19
Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast

Authors: Sarah Azouvi, Christian Cachin, Duc V. Le, Marko Vukolić, and Luca Zanolini

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Blockchain protocols implement total-order broadcast in a permissionless setting, where processes can freely join and leave. In such a setting, to safeguard against Sybil attacks, correct processes rely on cryptographic proofs tied to a particular type of resource to make them eligible to order transactions. For example, in the case of Proof-of-Work (PoW), this resource is computation, and the proof is a solution to a computationally hard puzzle. Conversely, in Proof-of-Stake (PoS), the resource corresponds to the number of coins that every process in the system owns, and a secure lottery selects a process for participation proportionally to its coin holdings. Although many resource-based blockchain protocols are formally proven secure in the literature, the existing security proofs fail to demonstrate why particular types of resources cause the blockchain protocols to be vulnerable to distinct classes of attacks. For instance, PoS systems are more vulnerable to long-range attacks, where an adversary corrupts past processes to re-write the history, than PoW and Proof-of-Storage systems. Proof-of-Storage-based and PoS-based protocols are both more susceptible to private double-spending attacks than PoW-based protocols; in this case, an adversary mines its chain in secret without sharing its blocks with the rest of the processes until the end of the attack. In this paper, we formally characterize the properties of resources through an abstraction called resource allocator and give a framework for understanding longest-chain consensus protocols based on different underlying resources. In addition, we use this resource allocator to demonstrate security trade-offs between various resources focusing on well-known attacks (e.g., the long-range attack and nothing-at-stake attacks).
Cite as

Sarah Azouvi, Christian Cachin, Duc V. Le, Marko Vukolić, and Luca Zanolini. Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{azouvi_et_al:LIPIcs.OPODIS.2022.19,
  author =	{Azouvi, Sarah and Cachin, Christian and Le, Duc V. and Vukoli\'{c}, Marko and Zanolini, Luca},
  title =	{{Modeling Resources in Permissionless Longest-Chain Total-Order Broadcast}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{19:1--19:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.19},
  URN =		{urn:nbn:de:0030-drops-176398},
  doi =		{10.4230/LIPIcs.OPODIS.2022.19},
  annote =	{Keywords: blockchain, consensus, resource, broadcast}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.44
Brief Announcement: How to Trust Strangers - Composition of Byzantine Quorum Systems

Authors: Orestis Alpos, Christian Cachin, and Luca Zanolini

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Trust is the basis of any distributed, fault-tolerant, or secure system. A trust assumption specifies the failures that a system, such as a blockchain network, can tolerate and determines the conditions under which it operates correctly. In systems subject to Byzantine faults, the trust assumption is usually specified through sets of processes that may fail together. Trust has traditionally been symmetric, such that all processes in the system adhere to the same, global assumption about potential faults. Recently, asymmetric trust models have also been considered, especially in the context of blockchains, where every participant is free to choose who to trust. In both cases, it is an open question how to compose trust assumptions. Consider two or more systems, run by different and possibly disjoint sets of participants, with different assumptions about faults: how can they work together? This work answers this question for the first time and offers composition rules for symmetric and for asymmetric quorum systems. These rules are static and do not require interaction or agreement on the new trust assumption among the participants. Moreover, they ensure that if the original systems allow for running a particular protocol (guaranteeing consistency and availability), then so will the joint system. At the same time, the composed system tolerates as many faults as possible, subject to the underlying consistency and availability properties. Reaching consensus with asymmetric trust in the model of personal Byzantine quorum systems (Losa et al., DISC 2019) was shown to be impossible, if the trust assumptions of the processes diverge from each other. With asymmetric quorum systems, and by applying our composition rule, we show how consensus is actually possible, even with the combination of disjoint sets of processes.
Cite as

Orestis Alpos, Christian Cachin, and Luca Zanolini. Brief Announcement: How to Trust Strangers - Composition of Byzantine Quorum Systems. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 44:1-44:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.DISC.2021.44,
  author =	{Alpos, Orestis and Cachin, Christian and Zanolini, Luca},
  title =	{{Brief Announcement: How to Trust Strangers - Composition of Byzantine Quorum Systems}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{44:1--44:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.44},
  URN =		{urn:nbn:de:0030-drops-148468},
  doi =		{10.4230/LIPIcs.DISC.2021.44},
  annote =	{Keywords: Byzantine quorum systems, composition of quorum systems, trust models, asymmetric trust}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.51
Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus

Authors: Christian Cachin and Luca Zanolini

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Among asynchronous, randomized, and signature-free implementations of consensus, the protocols of Mostéfaoui et al. (PODC 2014 and JACM 2015) represent a landmark result, which has been extended later and taken up in practical systems. The protocols achieve optimal resilience and take, in expectation, only a constant expected number of rounds and have quadratic message complexity. Randomization is provided through a common-coin primitive. However, the first version of this simple and appealing protocol suffers from a little-known liveness issue due to asynchrony. The JACM 2015 version avoids the problem, but is considerably more complex. This work revisits the original protocol of PODC 2014 and points out in detail why it may not progress. A fix for the protocol is presented, which does not affect any of its properties, but lets it regain the original simplicity in asynchronous networks enhanced with a common-coin protocol.
Cite as

Christian Cachin and Luca Zanolini. Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 51:1-51:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2021.51,
  author =	{Cachin, Christian and Zanolini, Luca},
  title =	{{Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{51:1--51:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.51},
  URN =		{urn:nbn:de:0030-drops-148535},
  doi =		{10.4230/LIPIcs.DISC.2021.51},
  annote =	{Keywords: Randomized consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.10
Security Analysis of Ripple Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes. Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions.
Cite as

Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić. Security Analysis of Ripple Consensus. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2020.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Mi\'{c}i\'{c}, Jovana},
  title =	{{Security Analysis of Ripple Consensus}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.10},
  URN =		{urn:nbn:de:0030-drops-134956},
  doi =		{10.4230/LIPIcs.OPODIS.2020.10},
  annote =	{Keywords: Ripple, Blockchain, Quorums, Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.7
Asymmetric Distributed Trust

Authors: Christian Cachin and Björn Tackmann

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory and broadcast primitives with processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust.
Cite as

Christian Cachin and Björn Tackmann. Asymmetric Distributed Trust. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.OPODIS.2019.7,
  author =	{Cachin, Christian and Tackmann, Bj\"{o}rn},
  title =	{{Asymmetric Distributed Trust}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.7},
  URN =		{urn:nbn:de:0030-drops-117933},
  doi =		{10.4230/LIPIcs.OPODIS.2019.7},
  annote =	{Keywords: Quorums, consensus, distributed trust, blockchains, cryptocurrencies}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.39
Brief Announcement: Asymmetric Distributed Trust

Authors: Christian Cachin and Björn Tackmann

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory and broadcast primitives with processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust.
Cite as

Christian Cachin and Björn Tackmann. Brief Announcement: Asymmetric Distributed Trust. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 39:1-39:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2019.39,
  author =	{Cachin, Christian and Tackmann, Bj\"{o}rn},
  title =	{{Brief Announcement: Asymmetric Distributed Trust}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{39:1--39:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.39},
  URN =		{urn:nbn:de:0030-drops-113460},
  doi =		{10.4230/LIPIcs.DISC.2019.39},
  annote =	{Keywords: Quorums, consensus, distributed trust, blockchains, cryptocurrencies}
}
Document
Keynote Talk
DOI: 10.4230/LIPIcs.DISC.2017.1
Blockchain Consensus Protocols in the Wild (Keynote Talk)

Authors: Christian Cachin and Marko Vukolic

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.
Cite as

Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2017.1,
  author =	{Cachin, Christian and Vukolic, Marko},
  title =	{{Blockchain Consensus Protocols in the Wild}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.1},
  URN =		{urn:nbn:de:0030-drops-80160},
  doi =		{10.4230/LIPIcs.DISC.2017.1},
  annote =	{Keywords: Permissioned blockchains, consensus, Byzantine fault-tolerance, snake oil, protocol analysis}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.2
Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract)

Authors: Christian Cachin

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A blockchain is a public ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Distributed protocols tolerating faults and adversarial attacks, coupled with cryptographic tools are needed for this. The recent interest in blockchains has revived research on consensus protocols, ranging from the proof-of-work method in Bitcoin's "mining" protocol to classical Byzantine agreement. Going far beyond its use in cryptocurrencies, blockchain is today viewed as a promising technology to simplify trusted exchanges of data and goods among companies. In this context, the Hyperledger Project has been established in early 2016 as an industry-wide collaborative effort to develop an open-source blockchain. This talk will present an overview of blockchain concepts, cryptographic building blocks and consensus mechanisms. It will also introduce Hyperledger Fabric, an implementation of blockchain technology intended for enterprise applications. Being one of the key partners in the Hyperledger Project, IBM is actively involved in the development of this blockchain platform.
Cite as

Christian Cachin. Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cachin:LIPIcs.OPODIS.2016.2,
  author =	{Cachin, Christian},
  title =	{{Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.2},
  URN =		{urn:nbn:de:0030-drops-70719},
  doi =		{10.4230/LIPIcs.OPODIS.2016.2},
  annote =	{Keywords: consensus, cryptographic, distributed protocols}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.24
Non-Determinism in Byzantine Fault-Tolerant Replication

Authors: Christian Cachin, Simon Schubert, and Marko Vukolic

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Service replication distributes an application over many processes for tolerating faults, attacks, and misbehavior among a subset of the processes. With the recent interest in blockchain technologies, distributed execution of one logical application has become a prominent topic. The established state-machine replication paradigm inherently requires the application to be deterministic. This paper distinguishes three models for dealing with non-determinism in replicated services, where some processes are subject to faults and arbitrary behavior (so-called Byzantine faults): first, the modular case that does not require any changes to the potentially non-deterministic application (and neither access to its internal data); second, master-slave solutions, where ties are broken by a leader and the other processes validate the choices of the leader; and finally, applications that use cryptography and secret keys. Cryptographic operations and secrets must be treated specially because they require strong randomness to satisfy their goals. The paper also introduces two new protocols. First, Protocol Sieve uses the modular approach and filters out non-deterministic operations in an application. It ensures that all correct processes produce the same outputs and that their internal states do not diverge. A second protocol, called Mastercrypt, implements cryptographically secure randomness generation with a verifiable random function and is appropriate for most situations in which cryptographic secrets are involved. All protocols are described in a generic way and do not assume a particular implementation of the underlying consensus primitive.
Cite as

Christian Cachin, Simon Schubert, and Marko Vukolic. Non-Determinism in Byzantine Fault-Tolerant Replication. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.OPODIS.2016.24,
  author =	{Cachin, Christian and Schubert, Simon and Vukolic, Marko},
  title =	{{Non-Determinism in Byzantine Fault-Tolerant Replication}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.24},
  URN =		{urn:nbn:de:0030-drops-70935},
  doi =		{10.4230/LIPIcs.OPODIS.2016.24},
  annote =	{Keywords: Blockchain, atomic broadcast, consensus, distributed cryptography, verifiable random functions}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2015
LIPIcs, Volume 46, OPODIS'15, Complete Volume

Authors: Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
LIPIcs, Volume 46, OPODIS'15, Complete Volume
Cite as

19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{anceaume_et_al:LIPIcs.OPODIS.2015,
  title =	{{LIPIcs, Volume 46, OPODIS'15, Complete Volume}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015},
  URN =		{urn:nbn:de:0030-drops-67174},
  doi =		{10.4230/LIPIcs.OPODIS.2015},
  annote =	{Keywords: Distributed Systems}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2015.0
Front Matter, Table of Contents, Preface, Committees, List of Authors

Authors: Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Front Matter, Table of Contents, Preface, Committees, List of Authors
Cite as

19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{anceaume_et_al:LIPIcs.OPODIS.2015.0,
  author =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  title =	{{Front Matter, Table of Contents, Preface, Committees, List of Authors}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.0},
  URN =		{urn:nbn:de:0030-drops-66223},
  doi =		{10.4230/LIPIcs.OPODIS.2015.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committees, List of Authors}
}
Document
DOI: 10.4230/DagSemProc.06371.1
06371 Abstracts Collection – From Security to Dependability

Authors: Christian Cachin, Felix C. Freiling, and Jaap-Henk Hoepman

Published in: Dagstuhl Seminar Proceedings, Volume 6371, From Security to Dependability (2007)

Abstract
From 10.09.06 to 15.09.06, the Dagstuhl Seminar 06371 ``From Security to Dependability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Christian Cachin, Felix C. Freiling, and Jaap-Henk Hoepman. 06371 Abstracts Collection – From Security to Dependability. In From Security to Dependability. Dagstuhl Seminar Proceedings, Volume 6371, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:DagSemProc.06371.1,
  author =	{Cachin, Christian and Freiling, Felix C. and Hoepman, Jaap-Henk},
  title =	{{06371 Abstracts Collection – From Security to Dependability}},
  booktitle =	{From Security to Dependability},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6371},
  editor =	{Christian Cachin and Felix C. Freiling and Jaap-Henk Hoepman},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06371.1},
  URN =		{urn:nbn:de:0030-drops-8532},
  doi =		{10.4230/DagSemProc.06371.1},
  annote =	{Keywords: Fault-tolerance, safety, distributed computing, language-based security, cryptography}
}
Document
DOI: 10.4230/DagSemProc.06371.2
06371 Executive Summary – From Security to Dependability

Authors: Christian Cachin, Felix C. Freiling, and Jaap-Henk Hoepman

Published in: Dagstuhl Seminar Proceedings, Volume 6371, From Security to Dependability (2007)

Abstract
This seminar brought together researchers and practitioners from the different areas of dependability and security, in particular, from fault-tolerance, safety, distributed computing, langelanguage-based security, and cryptography. The aim was to discuss common problems faced by research in these areas, the differences in their respective approaches, and to identify research challenges in this context.
Cite as

Christian Cachin, Felix C. Freiling, and Jaap-Henk Hoepman. 06371 Executive Summary – From Security to Dependability. In From Security to Dependability. Dagstuhl Seminar Proceedings, Volume 6371, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:DagSemProc.06371.2,
  author =	{Cachin, Christian and Freiling, Felix C. and Hoepman, Jaap-Henk},
  title =	{{06371 Executive Summary – From Security to Dependability}},
  booktitle =	{From Security to Dependability},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6371},
  editor =	{Christian Cachin and Felix C. Freiling and Jaap-Henk Hoepman},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06371.2},
  URN =		{urn:nbn:de:0030-drops-8512},
  doi =		{10.4230/DagSemProc.06371.2},
  annote =	{Keywords: Fault-tolerance, safety, distributed computing, language-based security, cryptography}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact